Recently there have been demands for technologies which enable enterprises to analyze large amounts of data and utilize the results of analysis to provide customers with new services. Such data might be distributed not only within one data center but also across a plurality of data centers. A KVS (Key-Value Store) is one type of storage that holds a large amount of data. The KVS is a simple database which enables users to store and read data (values) with a unique key.
Meanwhile, network bandwidth, especially WAN (Wide Area Network) bandwidth, has grown at a much smaller pace than the growth of data transmission. Therefore, for data distributed across devices at a plurality of locations, reduction in the amount of data communicated between locations is a major challenge.
One method for distributing a KVS across devices at a plurality of locations is discussed in “Hierarchical Peer-to-Peer Systems” (L. Garces-Erice, et al., Parallel Processing Letters 2003). In the hierarchical distributed hash table (DHT) technology disclosed in this paper, devices at a near location comprise a local DHT overlay, one device in each local DHT overlay is selected as a super node, and the super nodes comprise a global DHT overlay. A device can access any data stored not only in the same local DHT overlay but also in another local DHT overlay via the global DHT overlay. However, if a device requests data corresponding to a key, then the request is dispatched to all other local DHT overlays via the global DHT overlay even though some of local DHT overlays do not have data corresponding to the key. Therefore, unnecessary traffic flows between some locations.
U.S. pre-grant publication No. 2010/0332579 also discloses techniques for sharing content among peers by using a hierarchical DHT technology. According to this publication, local domains are organized into hierarchical clusters based on their proximity. A peer searches for a given piece of content in a proximity-guided manner and terminates at the earliest local domain which has the content. The publication assumes that there is a single name space of keys or content identifiers. However, each local domain may have its own name space. In this case, more than one content may have the same key or content identifier. The publication does not cope with such a case.